package leetcode.lt题型分类.并查集;

import leetcode.util.CommonUtils;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ：zsy
 * @date ：Created 2022/10/17 1:02 PM
 * @description：
 */
public class 可能的二分法 {
    @Test
    public void test() {
        CommonUtils.arrTransfer("[[1,2],[1,3],[2,4]]");
        int[][] nums = new int[][]{{1, 2}, {1, 3}, {2, 4}};
        System.out.println(Arrays.deepToString(nums));
        System.out.println(new Solution().possibleBipartition(4, nums));
    }


    class Solution {

        int n;

        public boolean possibleBipartition(int n, int[][] dislikes) {
            int[] fa = new int[n + 1];
            Arrays.fill(fa, -1);
            List<Integer>[] g = new List[n + 1];
            for (int i = 1; i <= n; i++) {
                g[i] = new ArrayList<>();
            }
            for (int[] dislike : dislikes) {
                g[dislike[0]].add(dislike[1]);
                g[dislike[1]].add(dislike[0]);
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j < g[i].size(); j++) {
                    unit(g[i].get(0), g[i].get(j), fa);
                    if (isConnect(i, g[i].get(j), fa)) {
                        return false;
                    }
                }
            }
            return true;
        }

        private boolean isConnect(int x, int y, int[] fa) {
            return findFa(x, fa) == findFa(y, fa);
        }

        private void unit(int x, int y, int[] fa) {
            x = findFa(x, fa);
            y = findFa(y, fa);
            if (x == y) return;
            if (fa[x] < fa[y]) {
                int tmp = x;
                x = y;
                y = tmp;
            }
            fa[x] += fa[y];
            fa[y] = x;
        }

        private int findFa(int x, int[] fa) {
            return fa[x] < 0 ? x : findFa(fa[x], fa);
        }
    }
}
